This month’s Challenge deals with the game of chess. You will be given a chess position and asked to produce the list of moves and captures that it is legal for one of the sides to make in accordance with the rules of chess. The objective is to produce the legal move list in minimum time.
Here are the prototypes for the routines you should write:
This Challenge will consist of one call to InitChess, followed by multiple calls to LegalChessMoves. The InitChess routine will not be timed, and may initialize up to 32K bytes of storage preallocated by my testbench and pointed to by privateDataPtr. Your program should not use any static storage besides that pointed to by privateDataPtr.
Each call to LegalChessMoves will provide a piecePositionArray containing numberOfPieces chess pieces. Each piece is described in a PiecePosition struct containing the ChessPiece, Side, and position. The position is provided as a Square struct containing a Row and a Col, where rowA represents the starting row for the White major pieces, and rowH the starting row for Black. The columns are numbered from left to right as viewed from the White side, so that (rowH, col4) is the starting square of the Black queen in a new game. The piecePositionArray will describe a legal set of chess piece positions, anything from the initial positions in a new game to an end-game position. No position will be provided that could not be reached during a chess game. Remember that due to past pawn promotions, a side may have (for example) more than one queen. You should generate the moves for the side provided in sideToMove. The privateDataPtr parameter will be the same pointer provided to InitChess.
LegalChessMoves should store in legalMoveArray the complete list of legal ChessMoves for the sideToMove. The legalMoveArray will be allocated by my testbench and will be large enough to hold all of the legal moves for the given chess position. You should describe each legal move/capture by placing the row/col location of the moving piece in fromSq and the rol/col of the destination in toSq. In addition, for each move, the Boolean moveIsCapture should be set to true if the move captures an opponent's piece (and set to false otherwise). Similarly, the Boolean opponentPlacedInCheck should be set to true if the move places the opponent in check (and set to false otherwise). The return value of the function should be the number of moves stored in legalMoveArray. In generating the list of legal moves, you should assume that castling moves or en passant pawn captures cannot occur. Remember that it is not legal to make a chess move which places or leaves the moving side's king in check. If the sideToMove has been checkmated and cannot move, LegalChessMoves should return zero.
This month brings one change to the rules of the contest. From now on, with apologies (and sympathies) to any MacPlus users still out there, the 68020 code generation option will be turned ON. This Challenge will be scored using the THINK C compiler and 68K instruction set, but future Challenges will include occasional use of the CodeWarrior compiler and/or the PowerPC instruction set. This month, you should also include the following pragmas in your code:
Have fun, and e-mail me if there are any questions.
-------------The Rules
Here’s how it works: Each month we present a new programming challenge here. First, write some code that solves the Challenge. Second, optimize your code (a lot). Then, submit your solution to MacTech magazine. We choose a winner based on code correctness, speed, size, and elegance (in that order) as well as the postmark of the answer. In the event of multiple equally desirable solutions, we'll choose one winner at random (with honorable mention, but no prize, given to the runner up). The prize for each month’s best solution is $50 and a limited-edition, “The Winner! MacTech Magazine Programming Challenge” T-shirt (not available in stores).
Unless stated otherwise in the problem statement, the following rules apply: All solutions must be in ANSI compatible C. We disqualify entries with any assembly in them. You may call any Mac Toolbox routine (e.g., NewPtr instead of malloc). Compiler code generation options will be set to disable FPU use (for 680x0 code) and to enable all available speed optimizations. The compiler to be used and the target instruction set (680x0 or PowerPC) will be stated in the problem. Limit your code to 60 characters per line; this helps with e-mail gateways and page layout.
You can get a head start on the challenge by reading the online version. We post it to the online services at the same time that we post source code. We make every effort to have it online no later than when the magazines are mailed, but we're unable to guarantee that it will be online by any given date.
Mark solutions “Attn: Programmer’s Challenge Solution” and send it by e-mail to one of the Programmer's Challenge addresses in the “How to Communicate With Us” section on p. 2. MacTech magazine reserves the right to publish any solution in the Programming Challenge of the Month. Authors grant MacTech Magazine the exclusive right to publish entries without limitation upon submission of each entry. While authors retain copyright for the code submitted, they grant readers a license to use the code submitted as part of larger works.
